package com.demo.java.OD451_500.OD478;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【流浪地球(E卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146407020
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 读取输入的第一行，包含发动机数量N和启动事件数量P
        String[] tmp1 = in.nextLine().split(" ");
        int[] nums = new int[tmp1.length];
        for (int i = 0; i < tmp1.length; i++) {
            nums[i] = Integer.parseInt(tmp1[i]);
        }
        int count = nums[0];  // 发动机数量
        // 创建数组保存发动机的启动时间，-1表示未启动
        int[] engines = new int[count];
        for (int i = 0; i < count; i++) {
            engines[i] = -1;  // 初始状态均为未激活
        }

        int start_cnt = nums[1];  // 启动事件的数量
        int minTime = Integer.MAX_VALUE;  // 用于计算最早启动的时间

        // 读取启动事件的信息
        for (int i = 0; i < start_cnt; i++) {
            String[] tmp2 = in.nextLine().split(" ");
            int[] nums1 = new int[tmp2.length];
            for (int j = 0; j < tmp2.length; j++) {
                nums1[j] = Integer.parseInt(tmp2[j]);
            }
            // 更新对应发动机的启动时间
            engines[nums1[1]] = nums1[0];
            minTime = Math.min(minTime, nums1[0]);
        }

        // 调用find函数开始模拟发动机的激活过程
        find(engines, minTime);
    }

    // 激活某个发动机的位置以及其相邻的发动机
    public static void activate(int[] engines, int index, int time, int count) {
        // 处理左边相邻的发动机
        int left = index - 1;
        if (index == 0) {
            left = count - 1;  // 左边是循环的
        }
        // 处理右边相邻的发动机
        int right = index + 1;
        if (index == count - 1) {
            right = 0;  // 右边是循环的
        }

        // 如果左边发动机未启动，则启动它
        engines[left] = engines[left] == -1 ? time : engines[left];
        // 如果右边发动机未启动，则启动它
        engines[right] = engines[right] == -1 ? time : engines[right];
    }

    // 模拟所有发动机的激活过程
    public static void find(int[] engines, int start) {
        int flag = 1;
        // 不断激活直到所有发动机都启动
        while (flag == 1) {
            for (int i = 0; i < engines.length; i++) {
                if (engines[i] == start) {
                    activate(engines, i, start + 1, engines.length);
                }
            }
            start++;
            int active_cnt = 0;
            // 统计已经启动的发动机数量
            for (int i = 0; i < engines.length; i++) {
                if (engines[i] != -1) {
                    active_cnt++;
                }
            }
            if (active_cnt == engines.length) {
                flag = 0;  // 如果所有发动机都启动，则结束
            }
        }

        // 找到最后启动的时间
        int maxTime = engines[0];
        for (int i = 0; i < engines.length; i++) {
            if (engines[i] > maxTime) {
                maxTime = engines[i];
            }
        }

        // 输出最后启动的发动机的位置
        int count = 0;
        String result = "";
        for (int i = 0; i < engines.length; i++) {
            if (maxTime == engines[i]) {
                result += i + " ";
                count++;
            }
        }
        System.out.println(count);  // 输出最后启动的发动机数量
        System.out.println(result.trim());  // 输出这些发动机的位置
    }
}